#include <cstdio>

int n, cnt, factor[ 30 ], factorn;

void dfs( int re, int step, int deep )
{
    int i;
    if ( deep & 1 )
        cnt += n / re;
    else
        cnt -= n / re;
    for ( i = step + 1; i < factorn; i++ )
        dfs( re * factor[ i ], i, deep + 1 );
}

void init( )
{
    int i = 2, p;
    factorn = 0;
    scanf("%d", &n);
    p = cnt = n;
    while ( p != 1 )
    {
        if ( p % i == 0 )
        {
            factor[ factorn++ ] = i;
            while ( p % i == 0 )
                p /= i;
        }
        i++;
    }
}

void work( )
{
    int i;
    for ( i = 0; i < factorn; i++ )
        dfs( factor[ i ], i, 0 );
    printf("%d\n", cnt);
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        work( );
    }
    return 0;
}
